package com.fenqing.leetcode.code.t700_800;

import com.fenqing.annotations.Execute;
import com.fenqing.core.Topic;

import java.util.*;

public class Topic752 extends Topic {
    /**
     * 构造器
     *
     * @param input1 输入
     * @param input2
     */
    public Topic752(String input1, String input2) {
        super(input1, input2);
    }

    @Execute
    public int openLock(String[] deadends, String target) {
        if ("0000".equals(target)) {
            return 0;
        }
        String chars = "0000";
        int count = 0;
        Set<String> dead = new HashSet<>();
        Collections.addAll(dead, deadends);
        if (dead.contains("0000")) {
            return -1;
        }
        Set<String> seed = new HashSet<>();
        seed.add(chars);
        Deque<String> deque = new ArrayDeque<>();
        deque.offer(chars);
        while (!deque.isEmpty()) {
            count++;
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                String pop = deque.poll();
                List<String> list = list(pop);
                for (String s : list) {
                    if (!seed.contains(s) && !dead.contains(s)) {
                        if (s.equals(target)) {
                            return count;
                        }
                        seed.add(s);
                        deque.add(s);
                    }
                }
            }
        }
        return -1;
    }

    public List<String> list(String str){
        char[] chars = str.toCharArray();
        List<String> chars1 = new ArrayList<>();
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            chars[i] = prev(ch);
            chars1.add(new String(chars));
            chars[i] = next(ch);
            chars1.add(new String(chars));
            chars[i] = ch;
        }
        return chars1;
    }

    public char next(char ch){
        return ch == '9' ? '0' : (char)(ch + 1);
    }

    public char prev(char ch){
        return ch == '0' ? '9' : (char)(ch - 1);
    }


    public static void main(String[] args) {
        Topic752 topic752 = new Topic752("[\"0201\",\"0101\",\"0102\",\"1212\",\"2002\"]", "0202");
        int run = topic752.run();
        System.out.println(run);
    }
}
